1. Field of the Invention
The invention relates in general to a computer-implemented method for generating placements for integrated circuits (ICs) and, in particular, to a method for generating placements for integrated circuits (ICs) with an analytical placement algorithm.
2. Description of the Prior Art
The placement problem is to place objects into one or more fixed dies such that no objects overlap with each other and some cost metric (e.g., wirelength) is optimized. Placement is a major step in physical design that has been studied for several decades. Although it is a classical problem, many modern design challenges have reshaped this problem. The modern placement problem becomes very tough because we need to handle large-scale designs.
In modern placement algorithms, analytical placement algorithms have been shown to be most effective for large-scale IC designs. Analytical placement formulates the placement problem as mathematical programming composed of an objective function and a set of placement constraints, and then optimizes the objective through analytical approaches.
In the objective function, wirelength is one of the important factors to be optimized. A well-known half-perimeter wirelength (HPWL) model is popularly used. Since HPWL is not differentiable, it is hard to perform the optimization. Consequently, some smooth wirelength models, such as quadratic model, logarithm-sum-exponential (LSE) model, and Chen-Harker-Kanzow-Smale (CHKS) model were proposed to approximate HPWL.
However, the problem with improving analytical modeling for wirelength still induces many research challenges. Thus it is desirable to develop an accurate and effective wirelength model for analytical placement.
Furthermore, in modern IC designs, three-dimensional integrated circuit (3D IC) technology has emerged as one of the most promising solutions for overcoming the challenges in interconnect and integration complexity in modern and next generation circuit designs. The 3D IC technology can effectively reduce global interconnect length and increase circuit performance; however, this technology brings some challenges with through-silicon vias (TSVs), used to make interconnections among different dies (layers), thermal effects, packaging, power delivery/density, etc.
In a generic 3D IC structure, each die is stacked on top of another and communicated by TSVs. These TSVs are responsible for the interconnections among devices on different layers, but they could cause some significant problems. Under current technologies, TSV pitches are very large compared to the sizes of regular metal wires; as a result, a large number of TSVs will consume significant silicon areas and degrade the yield and reliability of the final chip.
In addition, TSVs are usually placed at the whitespace among macro blocks or cells, and thus TSVs might affect the routing resource and increase the overall chip or package area. The significant silicon areas occupied by TSVs and the induced yield and reliability issues become critical problems for 3D IC placement.
By reusing modern 2D placement results, a folding/stacking based 3D placement method was proposed. This method performs layer re-assignment for cells to further improve 3D placement solutions.
Another partitioning-based approach integrates wirelength, temperature, TSV counts, and thermal effect into the mini-cut objective. As known for the 2D placement problem, however, a partitioning-based approach is not as competitive as an analytical one.
Also, a multilevel analytical placement method is proposed for 3D ICs to relax discrete layer assignment so that the movements of cells are continuous in the z-direction. Its basic idea is to use an inter-layer density penalty function to remove cells between layers; however, the area occupied by TSVs is not considered during placement.
In a short summary, traditionally TSVs are inserted during the routing stage by searching whitespace in the whole 3D IC, and thus quality of a routing result strongly depends on the remaining whitespace after placement stage. However, since the sizes of TSVs are not considered during placement, the efficiency of the approaches mentioned above is usually not good enough.
To improve the deficiency, a force-directed quadratic algorithm is proposed for placing cells and TSVs in a 3D IC. In this algorithm, cells are assigned into multiple dies in a partitioning stage first, and then the placement for cells and the insertion of TSVs are carried out on each die independently for wirelength optimization. To be more specific, cells will not be moved across dies for wirelength optimization during the placement with TSVs. However, this may limit the quality of layout results.
Therefore, what is needed is a method which can places cells in a 3D IC using an effective wirelength model, along with taking the sizes of TSVs into consideration. Consequently, a high-quality layout can be generated for the 3D IC.